/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package firstround2009;

import java.io.IOException;
import static chanlib.Chan_IO.*;

/**
 * @author robit
 */
public class CrossingTheRoad{
    /*
      All neccesary to be defined
      including:
      variable, inner class
    */
    // static int A;
    // static void B();
    // static class C

    /*
       One calculation fits all of the cases.
    */
    static void preReckon(){
        return;
    }

    /*
      calculate the answer
    */
    private static void reckon(int line) {
        int N=Int();
        int M=Int();
        int S[][]=new int[N][M];
        int W[][]=new int[N][M], T[][]=new int[N][M], P[][]=new int[N][M];

        for(int i=0;i<N;i++)
        for(int j=0;j<M;j++){
            S[i][j]=Int();W[i][j]=Int();T[i][j]=Int();
            P[i][j]=S[i][j]+W[i][j];
            T[i][j]%=P[i][j];
            T[i][j]-=P[i][j];
        }
        // Preprocess T[i][j]
        
                       
        long OPT[][][]=new long[N][M][4];
        
        for(int r=0;r<N;r++)
        for(int c=0;c<M;c++)
        for(int pt=0;pt<4;pt++)
            OPT[r][c][pt]=Integer.MAX_VALUE;
                
        // For row = N-1
        OPT[N-1][0][0]=0;
        for(int v=0;v<4*N*M;v++)
        for(int r=N-1;r>=0;r--)
        for(int c=0;c<M;c++){
            //println(r+","+c);
            long walk=1,wait=0;// walkin time
            // 0-->1,2
            long res=(OPT[r][c][0]-T[r][c])%P[r][c];
            if(res<S[r][c])wait=S[r][c]-res;
            else wait=0;
            OPT[r][c][1]=Math.min(OPT[r][c][0]+walk+wait,OPT[r][c][1]);
            if(res>=S[r][c])wait=P[r][c]-res;
            else wait=0;
            OPT[r][c][2]=Math.min(OPT[r][c][0]+walk+wait,OPT[r][c][2]);
            //1-->3
            res=(OPT[r][c][1]-T[r][c])%P[r][c];
            if(res>=S[r][c])wait=P[r][c]-res;
            else wait=0;
            OPT[r][c][3]=Math.min(OPT[r][c][1]+walk+wait,OPT[r][c][3]);
            //2-->3
            res=(OPT[r][c][2]-T[r][c])%P[r][c];
            if(res<S[r][c])wait=S[r][c]-res;
            else wait=0;
            OPT[r][c][3]=Math.min(OPT[r][c][2]+walk+wait,OPT[r][c][3]);

            walk=2;wait=0;
            if(r-1>=0){
                OPT[r-1][c][0]=Math.min(OPT[r][c][2]+walk+wait,OPT[r-1][c][0]);
                OPT[r-1][c][1]=Math.min(OPT[r][c][3]+walk+wait,OPT[r-1][c][1]);
            }
            if(r+1<N){
                OPT[r+1][c][2]=Math.min(OPT[r][c][0]+walk+wait,OPT[r+1][c][2]);
                OPT[r+1][c][3]=Math.min(OPT[r][c][1]+walk+wait,OPT[r+1][c][3]);
            }
            if(c-1>=0){
                OPT[r][c-1][3]=Math.min(OPT[r][c][2]+walk+wait,OPT[r][c-1][3]);
                OPT[r][c-1][1]=Math.min(OPT[r][c][0]+walk+wait,OPT[r][c-1][1]);
            }
            if(c+1<M){
                OPT[r][c+1][2]=Math.min(OPT[r][c][3]+walk+wait,OPT[r][c+1][2]);
                OPT[r][c+1][0]=Math.min(OPT[r][c][1]+walk+wait,OPT[r][c+1][0]);
            }            
        }
            
        //println(OPT[0][1][3]+ "finally");
        long ans = OPT[0][M-1][3];

        String output=String.format("Case #%d: %d",line,ans);
        writeln(output, OUTFILE);
        println(output);
        //writeln(String.format("N=%d K=%d\n%s", N, K, ans),ANALFILE);
        //println(output);
    }

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) throws IOException {
        /*
           Pre-computing for all cases
        */

        // Just in case!
        //preReckon();
        //while((char)read()!='P');

        /*
          Input-output
        */
        boolean test=false;
        boolean small=false;
        String prob="B";
        String filename;
        if(test) filename="test";
        else{
            if(small) filename=prob+"-small-practice";
            else filename=prob+"-large-practice";
        }
        try {
            /*
               Init IO,plus determination of input line number
             */
            int lineNums = initFileIO(filename);
            for (int i = 1; i <= lineNums; i++) {
                reckon(i);
            }
        } finally {
            endIO();
        }
    }

}
